package sliding_window

import (
	"fmt"
	"math"
)

/*
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
示例 2：
输入：s = "a", t = "a"
输出："a"
示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
*/

//滑动窗口框架
//最小覆盖子串：先寻找可行解，然后优化可行解，最终得到最优解
//在任意时刻，只有一个指针运动，而另一个保持静止,t 中可能出现重复的字符，所以我们要记录字符的个数。
func minWindow(s string, t string) string {

	//初始化
	need, window := make(map[byte]int), make(map[byte]int)
	//个数初始化
	for i := 0; i < len(t); i++ {
		need[t[i]]++
	}

	left, right, valid := 0, 0, 0
	//记录最小覆盖子串的起始索引及长度
	start, length := 0, math.MaxInt

	for right < len(s) {

		//扩大窗口
		// c是将移入窗口的字符
		c := s[right]
		//右移窗口
		right++
		//进行窗口内数据的一系列更新
		if _, ok := need[c]; ok {
			window[c]++
			if window[c] == need[c] {
				valid++ //有效计数
			}
		}

		//判断左侧窗口是否要收缩
		//说明t中所有字符已经被覆盖，已经得到一个可行的覆盖子串，该开始收缩窗口了
		for valid == len(need) {
			//更新最小覆盖子串
			if right-left < length {
				start = left
				length = right - left
			}
			//d 是将要移出窗口的字符
			d := s[left]
			//左移窗口，收缩窗口，得到可行解
			left++
			//进行窗口内数据的一系列更新，进行最小覆盖子串的更新，以得到最优解
			if _, ok := need[d]; ok {
				if window[d] == need[d] {
					valid--
				}
				window[d]--
			}
		}
	}

	//返回最小覆盖子串
	if length == math.MaxInt {
		return ""
	} else {
		//从start开始，截取length个字符
		return fmt.Sprintf(s[start : start+length])

	}
}

//12-9
